package problems;

public class Euler031 extends AbstractEuler {

	private static final int TOTAL_REQUIRED = 200;

	int[] denominations =	{200,	100,	50,	20,	10,	5,	2,	1};
	int[] nDenominations =	{0,		0,		0,	0,	0,	0,	0,	0};
	
	@Override
	public Number calculate() {
		return findCombinations(0);
	}
	
	private int findCombinations(int denomination) {
		if (denomination == denominations.length) return 0;
		int combinations = 0;
		for (nDenominations[denomination] = TOTAL_REQUIRED / denominations[denomination]; nDenominations[denomination] >= 0; nDenominations[denomination]--, resetSmaller(denomination)) {
			int sum = sum();
			if (sum < TOTAL_REQUIRED) {
				combinations += findCombinations(denomination+1);
			} else if (sum >= TOTAL_REQUIRED) {
				if (sum == TOTAL_REQUIRED) {
					combinations++;
				}
				continue;
			}
		}
		return combinations;
	}
	
	private void resetSmaller(int denomination) {
		for (int i = denomination + 1; i < denominations.length; i++) {
			nDenominations[i] = denominations[i] / TOTAL_REQUIRED;
		}
	}
	
	private int sum() {
		int sum = 0;
		
		for (int i = 0; i < denominations.length; i++) {
			sum += denominations[i] * nDenominations[i];
		}
		
		return sum;
	}

	@Override
	protected Number getCorrectAnswer() {
		return 73682;
	}

}
